Most computers contain a form of high-performance data-storage elements called registers, which need to be used effectively to achieve high performance at runtime. The process of choosing language elements to allocate instructions to registers and the data movement required to use them is called “register allocation.” Register allocation has a major impact on the ultimate quality and performance of codes. A poor allocation can degrade both code size and runtime performance. However, finding a truly optimal solution has been proven to be computationally intractable. Several general approaches for register allocation have been proposed. For example, register allocation by graph coloring was described by Chaitin, et al. in Computer Languages, Vol. 6, pp 47-57, and in U.S. Pat. No. 4,571,678, titled “Register Allocation and Spilling via Graph Coloring.”
While there are register allocation algorithms for finding good solutions in the prior art, they cannot directly apply to the machine that utilizes multiple register files and complex access constraints because the code insertion/replacement is required in the register allocation to validate the code with the allocated registers. This impacts the complexity of register allocation problems in the machine.